package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @DESCRIPTION: 98 、 验证二叉搜索树
 * @USER: wanfu
 * @DATE: 2025/4/25 星期五 11:37
 */
public class IsValidBST {


    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);

        n1.right = n2;
        n2.left = n3;
        boolean validBST = new IsValidBST().isValidBST(n1);

        System.out.println(validBST);
    }

    // 通过递归的方式解决
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        return dfs(root)[0] == 1;
    }


    public int[] dfs(TreeNode root) {
        int[] resList = {
                1, root.val, root.val
        };
        if (null != root.left) {
            int[] lefts = dfs(root.left);
            if (lefts[0] == 0 || lefts[1] >= root.val) resList[0] = 0;
            resList[1] = Math.max(resList[1], lefts[1]);
            resList[2] = Math.min(resList[2], lefts[2]);
        }

        if (null != root.right) {
            int[] rights = dfs(root.right);
            if (rights[0] == 0 || rights[2] < root.val) resList[0] = 0;
            resList[1] = Math.max(resList[1], rights[1]);
            resList[2] = Math.min(resList[2], rights[2]);
        }
        return resList;
    }
    // 能否实现在中序遍历的过程中记录上一个节点，实现使用O（1）的空间复杂度，并且能够少量的减小时间复杂度
    // 用递归的方式实现中序遍历，并且在这个过程中记录上一个节点的值，一旦发现逆序，则结束运行、返回结果
//    public boolean isValidBST(TreeNode root) {
//        Deque<TreeNode> stack = new LinkedList<>();
//        long preValue = Long.MIN_VALUE;
//        while (root != null || !stack.isEmpty()) {
//            while (root != null) {
//                stack.push(root);
//                root = root.left;
//            }
//            TreeNode top = stack.pop();
//            if (preValue != Long.MIN_VALUE && top.val <= preValue) {
//                return false;
//            }
//            preValue = top.val;
//            root = top.right;
//        }
//        return true;
//    }


    // 思路1、用O(n)的空间存储中序遍历结果，若发现逆序则结束
//    static List<Integer> preOrderList = new ArrayList<>();
//    public boolean isValidBST(TreeNode root) {
//        dfs(root);
//        for (int i = 1; i < preOrderList.size(); i++) {
//            if (preOrderList.get(i) < preOrderList.get(i - 1)) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    private void dfs(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        dfs(root.left);
//        preOrderList.add(root.val);
//        dfs(root.right);
//    }

}
